package leetcode_core.leetcode_1;

public class ReverseBetween {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //base-case
        if(left == 1){
            //相当于翻转前n个元素
           return reverseN(head,right);
        }
        //对于head.next来说,就是反转区间[m-1,n-1]
        //前进到翻转的起点触发base-case
        head.next = reverseBetween(head.next,left-1,right-1);
        return head;
    }

    ListNode successor =null;//后驱节点
    ListNode reverseN(ListNode head,int n){
        if(n==1){
            //记录第n+1个节点,后面要用,
            successor = head.next;
            return head;
        }
        //以head.next为起点,需要翻转前n-1个节点
        ListNode last = reverseN(head.next,n-1);
        head.next.next = head;
        //让反转之后的head节点和后面的节点连起来
        head.next=successor;
        return last;
    }
}
